\subsection{Notation}
\begin{frame}

\frametitle{SQL Operational Semantics: Notation}
\begin{description}[style=nextline]
\item[Table Schema]
$T(A_1,\dots,A_n)$
\item[Attribute]
$T.A$
\item[Type]
$Type(T.A)$
\item[Table Schema Instance]
$\multi{\mu_1, \mu_2, ..., \mu_m}$ such that $dom(\mu_i) = \{T.A_1,\dots, T.A_n \}$, and $\mu_i(T.A_j) \in type(T.A_j)$
\end{description}
\pause
Attributes $\rightarrow$ logic variables

Rows $\rightarrow$ logic substitutions
\end{frame}

\begin{frame}
\begin{description}[style=nextline]
\item[Concatenation] $\mu_1 \odot \mu_2$ for $\mu_1, \mu_2$ substitutions with disjoint domains.
\item[Concatenation for multisets] $S_1 \odot S_2  = \{ \nu \circ \mu \mid \nu \in S_1, \mu \in S_2\}$ for $S_1, S_2$ multisets of rows.

\item[Substitution] $e\mu$, for $e$ an expression and $\mu$ a substitution.  % aplicación de la sustitución mu a la expresíon e
\item[Substitution for multisets] $S\mu$ for a multiset of rows $S$ and a substitution $\mu$ represents the application of $\mu$ to each member of $S$
\end{description}
\end{frame}

\subsection{Definition}
\begin{frame}
\frametitle{SQL Operational Semantics: Definition}
\begin{description}[style=nextline]
\item[View] \cod{create view V($A_1$, \dots, $A_n$) as \  $Q$} % Q query, A_1 ... A_n atribute names

With Q a query, either a basic query, an union or intersection of queries.
\item[Basic Query] \cod{ Q = select $e_1$, \dots, $e_n$ from $R_1\ B_1$ , \dots, $R_m \ B_m$  where $C$}

With
\begin{description}
\item[$R_1 \ B_1 \dots R_m B_m$]  Tables or views and its renames, 

\item[$e_1 \dots e_n$] expressions involving constants, predefined functions and attributes,

\item[$C$] Boolean expression, including $\cod{false} \mid  \cod{true} \mid e_1 \diamond e_2 \mid  C_1\ \cod{ and }\ C_2 \mid  C_1\ \cod{ or }\ C_2 \mid  \cod{ not }\, C1 \mid \cod{exists(Q)}$  with $e_1, e_2$ arithmetic expressions,  $\diamond \in \{ =, <>, >, <, >=, <= \}$,  $C_1$, $C_2$ SQL conditions and $Q$ an SQL query.
\end{description}
\item [Unions] of the form $Q_1$ \cod{union} $Q_2$, with $Q_1$ and $Q_2$ queries.

\item [Intersections] of the form $Q_1$ \cod{intersects} $Q_2$, with $Q_1$ and $Q_2$ queries. 
\end{description}
\end{frame}

\begin{frame}{Dependency tree}
The \emph{syntactic dependency tree} for a view, table or query $R$, with $R$ in the root of this tree, is defined as:
\begin{itemize}
\item If $R$ is a table it has no children.
\item If $R$ is a view the only child is the syntactic dependency tree of its associated query.
\item If $R$ is a query the children are the syntactic dependency trees of the relations occurring in the \cod{from} section, plus one child for each subquery occurring in the \cod{where} section.
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{SQL Operational Semantics}
Let $\mathcal{D}$ a relational database schema and $d$ be an instance of $\mathcal{D}$ Then we define our SQL Operational Semantics (SOS) as follows:
\begin{itemize}
\item For any table $T$ defined in $\mathcal{D}$,  $\SQL{T,d} = d(T)$.
\item If $Q$ is a query of the form \cod{$Q_1$ union $Q_2$}, then $\SQL{Q,d} = \SQL{Q1,d} \cup \SQL{Q2,d}$ with $\cup$ the union multiset operator.


\item   Analogously, if $Q$ is of the form \cod{$Q_1$ intersection $Q_2$} then, $\SQL{Q,d} = \SQL{Q1,d} \cap \SQL{Q2,d}$), with $\cap$ the intersection multiset operator.
\end{itemize}
\end{frame}
\begin{frame}
\begin{itemize}
\item For any simple query $Q$\\
        select $e_1$, \dots, $e_n$ from $R_1\ B_1$ , \dots, $R_m \ B_m$  where $C$;
        \begin{description}
 
        \item[$\SQL{Q,d}$]$ = \{ s_Q(\mu) \mid $\\
        $\nu_1 \in \SQL{R_1,d}, \dots, \nu_m \in \SQL{R_m,d},$,\\$  \mu = {\nu_1}^{B_1} \odot \cdots \odot {\nu_m}^{B_m}, \SQL{C\mu,d} \}$\\


        \item[$s_Q(\mu)$] = $\{Q.A_1 \mapsto (e_1 \mu), \dots, Q.A_n \mapsto (e_n \mu) \}$
          \end{description}
\begin{center}
{\small \begin{tabular}{c|c}
\textbf{Condition Type}&\textbf{$\SQL{C,d}$} \\
\hline
\textbf{false} & $\bot$ \\
\textbf{true} & $\top$  \\
\textbf{Arithmetic expression e} & $e$ \\
\textbf{$e_1 \diamond e_2$} & $(\SQL{e_1,d} \diamond \SQL{e_2,d})$ \\
\textbf{$ C_1\ \cod{ and }\ C_2$} & $ \SQL{C_1,d} \wedge \SQL{C_2,d}$ \\
\textbf{$ C_1\ \cod{ or }\ C_2$} &  $ \SQL{C_1,d} \vee \SQL{C_2,d}$  \\
\textbf{not $C$} &  $\neg \SQL{C,d}$ \\ 
\textbf{Exists $Q$} & $ \SQL{Q, d} \neq \emptyset$
\end{tabular}}
\end{center}
\item For any view $V$ with definition \cod{create view V($E_1$, \dots, $E_n$) as Q},
  $\SQL{V,d} = \SQL{Q,d} \{V.E_1 \mapsto Q.A_1, \dots, V.E_n \mapsto Q.A_n\}$.

\end{itemize}
\end{frame}

\subsection{Examples}
\begin{frame}[fragile]{SQL Operational Semantics: Example 1}
\begin{verbatim}
CREATE TABLE Grades (ID int, grade int);
CREATE VIEW Excellent (ExcellentID)
  AS SELECT ID from Grades
  WHERE grade >= 9);
\end{verbatim}
 $d(Grades)= \multi{(ID \mapsto 1,grade \mapsto 7),(ID \mapsto 2, grade \mapsto 9)}$ \\
\begin{itemize}
\item $\SQL{Grades,d} = d(Grades) $
\item $\SQL{Excellent,d} = \SQL{Q,d} \{Excellent.ExcellentID \mapsto Q.ID\} =$\\
$   \multi{ Q.ID \mapsto Grades.ID  \mid \nu_1 \in \SQL{Grades,d} ,\mu = \nu_1, \SQL{(grade >=9)\mu,d} }$\\
$\{Excellent.ExcellentID \mapsto Q.ID\}=$ $= \multi{Q.ID \mapsto 2} \{Excellent.ID \mapsto Q.ID\} = \multi{(Excellent.ID \mapsto 2)}$
\end{itemize}

\end{frame}